//
//  912. 排序数组.swift
//  手撕
//
//  Created by xiaoZuDeMeng on 2024/2/25.
//

import Foundation

//https://leetcode.cn/problems/sort-an-array/description/
//给你一个整数数组 nums，请你将该数组升序排列。
//
//
//
//示例 1：
//
//输入：nums = [5,2,3,1]
//输出：[1,2,3,5]
//示例 2：
//
//输入：nums = [5,1,1,2,0,0]
//输出：[0,0,1,1,2,5]
//
//
//提示：
//
//1 <= nums.length <= 5 * 104
//-5 * 104 <= nums[i] <= 5 * 104

// 超时
func 冒泡排序(_ nums: [Int]) -> [Int] {
    var array = nums
    for index in 0..<array.count {
        for j in 0..<array.count - index - 1 {
            if array[j] > array[j + 1] {
                array.swapAt(j, j + 1)
            }
        }
    }
    return array
}

func 插入排序(_ nums: [Int]) -> [Int] {
    if nums.count <= 1 {
        return nums
    }
    var array = nums
    for i in 1..<array.count {
        // 当前遍历，需要比较的数字value
        let value = array[i]
        var j = i - 1
        // 遍历value前面的数组，j不停变小
        while j >= 0 {
            if array[j] > value {
                array[j + 1] = array[j]
            } else {
                // 没有比此更小的，不需要操作
                break
            }
            j -= 1
        }
        // 最后定位到value的位置
        array[j + 1] = value
    }
    return array
}

// 超时
func 选择排序(_ nums: [Int]) -> [Int] {
    if nums.count <= 1 {
        return nums
    }
    var array = nums
    // 最后一次不需要遍历，因为只剩下一个元素了
    for i in 0..<array.count - 1 {
        // 未排序最小值，默认取已排序的最后一个元素
        var temp = array[i]
        // 用于定位最小值角标
        var minIndex = i
        for j in i + 1 ..< array.count {
            if temp > array[j] {
                temp = array[j]
                minIndex = j
            }
        }
        array.swapAt(i, minIndex)
    }
    return array
}

func 归并排序(_ nums: [Int]) -> [Int] {
  if nums.count <= 1 {
    return nums
  }
  var arr = nums
  merge_sort_c(&arr, 0, arr.count-1)
  return arr
}

func merge_sort_c(_ nums:inout [Int], _ left :Int, _ right:Int) {
  if left >= right {
    return
  }
  let point = (left+right)/2
  merge_sort_c(&nums, left, point)
  merge_sort_c(&nums,point+1,right)
  //! 合并
  merge_arr(&nums,left,point,right)
}

func merge_arr(_ nums:inout [Int], _ left :Int, _ point:Int, _ right:Int) {
  var i = left
  var j = point+1
  var k = 0
  var arr = [Int](repeating: 0, count: right-left+1)

  while i <= point && j <= right {
    if nums[i] <= nums[j] {
      arr[k] = nums[i]
      i += 1
    } else {
      arr[k] = nums[j]
      j += 1
    }
    k += 1
  }

  if i == point + 1 {
    while j <= right {
      arr[k] = nums[j]
      k += 1
      j += 1
    }
  } else {
    while i <= point {
      arr[k] = nums[i]
      k+=1
      i+=1
    }
  }

  for index in 0..<arr.count {
    nums[left+index] = arr[index]
  }
}

// 需要优化下，否则会超时
func 快速排序法(_ nums: [Int]) -> [Int] {
    var sortedNums = nums
    quickSort(&sortedNums, 0, sortedNums.count - 1)
    return sortedNums
}

func quickSort(_ nums: inout [Int], _ start: Int, _ end: Int) {
    if start >= end {
        return
    }
    
    // 优化1：选择合适的基准元素（这里选择中间元素）
    let pivotIndex = start + (end - start) / 2
    let pivot = nums[pivotIndex]
    
    // 将基准元素放到数组末尾
    nums.swapAt(pivotIndex, end)
    
    // 优化2：针对小规模子数组使用插入排序
    if end - start + 1 < 10 {
        insertionSort(&nums, start, end)
    } else {
        let partitionIndex = partition(&nums, start, end, pivot)
        quickSort(&nums, start, partitionIndex - 1)
        quickSort(&nums, partitionIndex + 1, end)
    }
}

func partition(_ nums: inout [Int], _ start: Int, _ end: Int, _ pivot: Int) -> Int {
    var i = start
    
    for j in start..<end {
        if nums[j] <= pivot {
            nums.swapAt(i, j)
            i += 1
        }
    }
    
    nums.swapAt(i, end)
    return i
}

func insertionSort(_ nums: inout [Int], _ start: Int, _ end: Int) {
    for i in (start+1)...end {
        let current = nums[i]
        var j = i - 1
        
        while j >= start && nums[j] > current {
            nums[j+1] = nums[j]
            j -= 1
        }
        
        nums[j+1] = current
    }
}
